package com.study.daily.algozuo.y2021.m12.day1222;

/**
 * MinStacks
 *
 * @author Tom on 2021/12/22
 */
public class Code01_MinStacks {

    public static int minStacks(String[] stacks, String target) {
        int ans = process1(stacks, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process1(String[] stacks, String target) {
        int size = stacks.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            String afterMinus = minus(stacks[i], target);
            if (afterMinus.length() != target.length()) {
                min = Math.min(min, process1(stacks, afterMinus));
            }
        }
        return min == Integer.MAX_VALUE ? min : 1 + min;
    }

    public static String minus(String stack, String target) {
        int[] sCount = new int[26];
        int[] tCount = new int[26];
        for (char ch : stack.toCharArray()) {
            sCount[ch - 'a']++;
        }
        for (char ch : target.toCharArray()) {
            tCount[ch - 'a']--;
        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            int size = tCount[i];
            if (size > 0) {
                for (int j = 0; j < size; j++) {
                    str.append((char) ('a' + i));
                }
            }
        }
        return str.toString();
    }

    public static int minStacks2(String[] stacks, String target){
        int N = stacks.length;
        int[][] sCount = new int[N][26];
        for(int i = 0; i < stacks.length; i++){
            for(char ch : stacks[i].toCharArray()){
                sCount[i][ch - 'a']++;
            }
        }
        int ans = process2(sCount, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process2(int[][] sCount, String target){

        // 统计target的字符个数
        int[] tCount = new int[26];
        for(char ch: target.toCharArray()){
            tCount[ch-'a']++;
        }
        int min = Integer.MAX_VALUE;
        // 统计在stacks的数组中包含target的情况下,使用的贴纸的张数
        for(int i = 0; i < sCount.length; i++){
            int[] stack = sCount[i];
            // 可以扣减的情况下,去除无效扣减
            if(stack[target.toCharArray()[0] - 'a'] > 0){
                StringBuilder str = new StringBuilder();
                for(int j = 0; j < 26; j++){
                    int num = tCount[j] - stack[j];
                    if(num > 0){
                        for(int k = 0; k < num; k++){
                            str.append((char)('a' + j));
                        }
                    }
                }
                min = Math.min(min, process2(sCount,str.toString()));
            }
        }
        return min == Integer.MAX_VALUE ? min: min + 1;
    }
}
